Định lý: Đồ thị K 3 , 3 {\displaystyle K_{3,3}} không phải là đồ thị phẳng.

Chứng minh: Giả sử K 3 , 3 {\displaystyle K_{3,3}} là đồ thị phẳng. Khi đó ta có một đồ thị phẳng với 6 đỉnh (n=6) và 9 cạnh (p=9), nên theo hệ thức Euler đồ thị có số miền là d = p-n+2 = 5. Ở đây, mỗi cạnh chung cho hai miền. Bằng kiểm tra trực tiếp ta thấy không thể có miền tạo ra từ 3 cạnh, do đó mỗi miền có ít nhất 4 cạnh. Do đó 4d ≤ 2p, tức là 4x5 ≤ 2x9, vô lý.

Như vậy định lý này cho ta lời giải của bài toán "Ba nhà ba giếng", nghĩa là không thể thực hiện được việc làm các đường khác đến giếng sao cho các đường này đôi một không giao nhau.

Định lý: Đồ thị K 5 {\displaystyle K_{5}} không phải là đồ thị phẳng.

Chứng minh: Giả sử K 5 {\displaystyle K_{5}} là đồ thị phẳng. Khi đó ta có một đồ thị phẳng với 5 đỉnh (n=5) và 10 cạnh (p=10), nên theo hệ thứcEuler đồ thị có số miền là d=p-n+2=7. Trong K 5 {\displaystyle K_{5}} , mỗi miền có ít nhất 3 cạnh, mỗi cạnh chung cho 2 miền, vì vậy 3d ≤ 2n, tức là 3x7 ≤ 2x10, vô lý.